{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Replace Words"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #trie #array #hash-table #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #字典树 #数组 #哈希表 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: replaceWords"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #单词替换"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>在英语中，我们有一个叫做&nbsp;<code>词根</code>(root) 的概念，可以词根<strong>后面</strong>添加其他一些词组成另一个较长的单词——我们称这个词为&nbsp;<code>继承词</code>(successor)。例如，词根<code>an</code>，跟随着单词&nbsp;<code>other</code>(其他)，可以形成新的单词&nbsp;<code>another</code>(另一个)。</p>\n",
    "\n",
    "<p>现在，给定一个由许多<strong>词根</strong>组成的词典 <code>dictionary</code> 和一个用空格分隔单词形成的句子 <code>sentence</code>。你需要将句子中的所有<strong>继承词</strong>用<strong>词根</strong>替换掉。如果<strong>继承词</strong>有许多可以形成它的<strong>词根</strong>，则用<strong>最短</strong>的词根替换它。</p>\n",
    "\n",
    "<p>你需要输出替换之后的句子。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>dictionary = [\"cat\",\"bat\",\"rat\"], sentence = \"the cattle was rattled by the battery\"\n",
    "<strong>输出：</strong>\"the cat was rat by the bat\"\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>dictionary = [\"a\",\"b\",\"c\"], sentence = \"aadsfasf absbs bbab cadsfafs\"\n",
    "<strong>输出：</strong>\"a a b c\"\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= dictionary.length&nbsp;&lt;= 1000</code></li>\n",
    "\t<li><code>1 &lt;= dictionary[i].length &lt;= 100</code></li>\n",
    "\t<li><code>dictionary[i]</code>&nbsp;仅由小写字母组成。</li>\n",
    "\t<li><code>1 &lt;= sentence.length &lt;= 10^6</code></li>\n",
    "\t<li><code>sentence</code>&nbsp;仅由小写字母和空格组成。</li>\n",
    "\t<li><code>sentence</code> 中单词的总量在范围 <code>[1, 1000]</code> 内。</li>\n",
    "\t<li><code>sentence</code> 中每个单词的长度在范围 <code>[1, 1000]</code> 内。</li>\n",
    "\t<li><code>sentence</code> 中单词之间由一个空格隔开。</li>\n",
    "\t<li><code>sentence</code>&nbsp;没有前导或尾随空格。</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [replace-words](https://leetcode.cn/problems/replace-words/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [replace-words](https://leetcode.cn/problems/replace-words/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[\"cat\",\"bat\",\"rat\"]\\n\"the cattle was rattled by the battery\"', '[\"a\",\"b\",\"c\"]\\n\"aadsfasf absbs bbab cadsfafs\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Node:\n",
    "    def __init__(self,depth):\n",
    "        self.end= False\n",
    "        self.depth = depth\n",
    "        self.childs = {}\n",
    "    \n",
    "    def build(self,word):\n",
    "        if self.end:\n",
    "            return \n",
    "        if self.depth==len(word):\n",
    "            self.end=True\n",
    "            return\n",
    "        if not self.childs.get(word[self.depth],None):\n",
    "            self.childs[word[self.depth]]=Node(self.depth+1)\n",
    "        self.childs[word[self.depth]].build(word)\n",
    "            \n",
    "    def find(self,word):\n",
    "        if self.end:\n",
    "            return word[0:self.depth]\n",
    "        else:\n",
    "            if self.depth <len(word) and self.childs.get(word[self.depth],None):\n",
    "                return self.childs[word[self.depth]].find(word)\n",
    "            else:\n",
    "                return False\n",
    "\n",
    "class Solution:\n",
    "    def replaceWords(self, dict, sentence):\n",
    "        \"\"\"\n",
    "        :type dict: List[str]\n",
    "        :type sentence: str\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        ans =[]\n",
    "        root = Node(0)\n",
    "        for word in dict:\n",
    "            root.build(word)\n",
    "        for word in sentence.split():\n",
    "            a = root.find(word)\n",
    "            if a:\n",
    "                ans.append(a)\n",
    "            else:\n",
    "                ans.append(word)\n",
    "        return ' '.join(ans)\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceWords(self, dict, sentence):\n",
    "        \"\"\"\n",
    "        :type dict: List[str]\n",
    "        :type sentence: str\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        dict.sort(key=len)\n",
    "        ans = []\n",
    "        for word in sentence.split():\n",
    "            for root in dict:\n",
    "                if word.startswith(root):\n",
    "                    ans.append(root)\n",
    "                    break\n",
    "            else:\n",
    "                ans.append(word)\n",
    "        return ' '.join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceWords(self,dic,sentence):\n",
    "        sentence_list=sentence.split()\n",
    "        for i in dic:\n",
    "            for j in range(len(sentence_list)):\n",
    "                if i == sentence_list[j][:len(i)]:\n",
    "                    sentence_list[j]=i\n",
    "        if len(sentence_list)==1:\n",
    "            return sentence_list[0]\n",
    "        res=''\n",
    "        for i in sentence_list[:-1]:\n",
    "            res+=i\n",
    "            res+=' '\n",
    "        res+=sentence_list[-1]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceWords(self, dict: List[str], sentence: str) -> str:\n",
    "        dict.sort(key = lambda root:len(root))\n",
    "        sentence = sentence.split(' ')\n",
    "        ret = []\n",
    "        for word in sentence:\n",
    "            flag = True\n",
    "            for root in dict:         \n",
    "                if word[:len(root)] == root:\n",
    "                    ret.append(root)\n",
    "                    flag = False\n",
    "                    break\n",
    "            if flag:\n",
    "                ret.append(word)\n",
    "        return ' '.join(ret)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceWords(self, dict: List[str], sentence: str) -> str:\n",
    "        dict.sort(key=lambda x:len(x))\n",
    "        r = []\n",
    "        for w in sentence.split():\n",
    "            r.append(w)\n",
    "            for d in dict:\n",
    "                if w.find(d)==0:\n",
    "                    r.pop()\n",
    "                    r.append(d)\n",
    "                    break\n",
    "        return \" \".join(r)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceWords(self, dictionary: List[str], sentence: str) -> str:\n",
    "        prefixs = sorted(dictionary, key=lambda x: len(x))\n",
    "        words = sentence.split()\n",
    "        results = []\n",
    "        for word in words:\n",
    "            for prefix in prefixs:\n",
    "                if word.startswith(prefix):\n",
    "                    results.append(prefix)\n",
    "                    break\n",
    "            else:\n",
    "                results.append(word)\n",
    "        return ' '.join(results)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceWords(self, dictionary: List[str], sentence: str) -> str:\n",
    "        new_sentece = sentence.split(\" \")\n",
    "        dictionary.sort(key = lambda x: len(x))\n",
    "        n = len(new_sentece)\n",
    "        for root in dictionary:\n",
    "            length = len(root)\n",
    "            for j in range(n):\n",
    "                if new_sentece[j][0:length] == root:\n",
    "                    new_sentece[j] = root\n",
    "                    \n",
    "        print(new_sentece)\n",
    "        return \" \".join(new_sentece)\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceWords(self, dictionary: List[str], sentence: str) -> str:\n",
    "        ans=[]\n",
    "        dic=set(dictionary)\n",
    "        for word in sentence.split(' '):\n",
    "            i=0\n",
    "            while i<len(word):\n",
    "                if word[:i] in dic:\n",
    "                    ans.append(word[:i])\n",
    "                    break\n",
    "                i+=1\n",
    "            #print (i,word)\n",
    "            if i==len(word):\n",
    "                ans.append(word[:])\n",
    "        #print (ans)\n",
    "        return ' '.join(ans)\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceWords(self, dictionary: List[str], sentence: str) -> str:\n",
    "        result = \"\"\n",
    "        tmp = \"\"\n",
    "        i = 0\n",
    "        while i < len(sentence):\n",
    "            if sentence[i] == \" \":\n",
    "                result += tmp\n",
    "                result += \" \"\n",
    "                tmp = \"\"\n",
    "                i += 1\n",
    "                continue\n",
    "            tmp += sentence[i]\n",
    "            if tmp in dictionary:\n",
    "                result += tmp\n",
    "                tmp = \"\"\n",
    "                flag = False\n",
    "                for j in range(i + 1,len(sentence)):\n",
    "                    if sentence[j] == \" \":\n",
    "                        result += \" \"\n",
    "                        flag = True\n",
    "                        break\n",
    "                if flag == False:\n",
    "                    break\n",
    "                else:\n",
    "                    i = j + 1\n",
    "                    continue\n",
    "            i += 1\n",
    "        if tmp != \"\":\n",
    "            result += tmp\n",
    "        return result\n",
    "            \n",
    "            \n",
    "            \n",
    "                  \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceWords(self, dictionary: List[str], sentence: str) -> str:\n",
    "        sentence=sentence+\" \"\n",
    "        s,d=\"\",\"\"\n",
    "        for i in sentence:\n",
    "            if i!=\" \":\n",
    "                d=d+i \n",
    "            else:\n",
    "                for j in dictionary:\n",
    "                    if len(j)<len(d) and d[:len(j)]==j:\n",
    "                        d=j\n",
    "                s=s+d+\" \"\n",
    "                d=\"\"\n",
    "        return s[:-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceWords(self, dictionary: List[str], sentence: str) -> str:\n",
    "        words = sentence.split(' ')\n",
    "        res = []\n",
    "        for word in words:\n",
    "            tmp = []\n",
    "            for dic in dictionary:\n",
    "                if dic in word and word.index(dic) == 0:\n",
    "                    tmp.append(dic)\n",
    "            if not tmp:\n",
    "                res.append(word)\n",
    "            else:\n",
    "                tar = 0\n",
    "                for i in range(1, len(tmp)):\n",
    "                    if len(tmp[tar]) > len(tmp[i]):\n",
    "                        tar = i\n",
    "                res.append(tmp[tar])\n",
    "        return ' '.join(res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceWords(self, dictionary: List[str], sentence: str) -> str:\n",
    "        words = sentence.split(' ')\n",
    "        res = []\n",
    "        for word in words:\n",
    "            tmp = []\n",
    "            for dic in dictionary:\n",
    "                if dic in word and word.index(dic) == 0:\n",
    "                    tmp.append(dic)\n",
    "            if not tmp:\n",
    "                res.append(word)\n",
    "            else:\n",
    "                tar = 0\n",
    "                for i in range(1, len(tmp)):\n",
    "                    if len(tmp[tar]) > len(tmp[i]):\n",
    "                        tar = i\n",
    "                res.append(tmp[tar])\n",
    "        return ' '.join(res)\n",
    "                        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceWords(self, dictionary: List[str], sentence: str) -> str:\n",
    "        dictionary.sort()\n",
    "        dictionary_dict=dict()\n",
    "        sentence_list=sentence.split(\" \")\n",
    "        m=len(sentence_list)\n",
    "        sentence_list_index=[0]*m\n",
    "        for vab in dictionary:\n",
    "            paras=re.compile(f'{vab}')\n",
    "            for i in range(m):\n",
    "                if paras.match(sentence_list[i]) and sentence_list_index[i]==0:\n",
    "                    dictionary_dict[sentence_list[i]]=vab\n",
    "                    sentence_list_index[i]=1\n",
    "        for i in range(len(sentence_list)):\n",
    "            if  dictionary_dict.get(sentence_list[i]) !=None:\n",
    "                sentence_list[i]=dictionary_dict.get(sentence_list[i])\n",
    "        return \" \".join(sentence_list)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import re\n",
    "class Solution:\n",
    "    def replaceWords(self, dictionary: List[str], sentence: str) -> str:\n",
    "        dictionary.sort(key=lambda x:len(x))\n",
    "        senList = sentence.split(' ')\n",
    "        flag = [0 for i in range(len(senList))]\n",
    "        for i in range(len(dictionary)):\n",
    "            for j in range(len(flag)):\n",
    "                if flag[j] != 1 and re.match(dictionary[i], senList[j]):\n",
    "                    senList[j] = dictionary[i]\n",
    "                    flag[j] = 1\n",
    "        return ' '.join(senList)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceWords(self, dictionary: List[str], sentence: str) -> str:\n",
    "        dictionary.sort(key=lambda x: len(x))\n",
    "        sentence = ' ' + sentence + ' '\n",
    "        for pre in dictionary:\n",
    "            key_word = ' ' + pre\n",
    "            while sentence.find(key_word) != -1:\n",
    "                start_idx = sentence.find(key_word)\n",
    "                temp_idx = sentence[start_idx+1:].find('#')\n",
    "                if temp_idx != -1:\n",
    "                    end_idx = min(sentence[start_idx+1:].find(' '), sentence[start_idx+1:].find('#')) +start_idx+1\n",
    "                else:\n",
    "                    end_idx = sentence[start_idx+1:].find(' ') + start_idx+1\n",
    "                sentence = sentence[0:start_idx] + '#' +key_word[1:] + sentence[end_idx:]\n",
    "        rslt = sentence.replace('#', ' ')\n",
    "        return rslt[1:-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 方法一：哈希集合\n",
    "class Solution:\n",
    "    def replaceWords(self,dictionary:list[str],sentence:str)->str:\n",
    "        dictionarySet=set(dictionary)\n",
    "        word_list=sentence.split()\n",
    "        for i,word in enumerate(word_list):\n",
    "            # 如果一个单词匹配多个前缀，选择最短的一个\n",
    "            for j in range(1,len(word)+1):\n",
    "                if word[:j] in dictionarySet:\n",
    "                    word_list[i]=word[:j]\n",
    "                    break\n",
    "        return ' '.join(word_list)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceWords(self, dictionary: List[str], sentence: str) -> str:\n",
    "        dictionary.sort(key=lambda x:len(x))\n",
    "        s=sentence.split(' ')\n",
    "        for i in s:\n",
    "            for d in dictionary:\n",
    "                if d==i[0:len(d)]:\n",
    "                    sentence=sentence.replace(i,d,1)\n",
    "                    break\n",
    "        return sentence"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceWords(self, dictionary: List[str], sentence: str) -> str:\n",
    "        sentence = sentence.split(' ')\n",
    "        ans = ''\n",
    "        dictionary.sort()\n",
    "        for ele in sentence:\n",
    "            add=0\n",
    "            for dic in dictionary:\n",
    "                if ele.startswith(dic):\n",
    "                    ans =ans + ' ' + dic\n",
    "                    add=1\n",
    "                    break\n",
    "            if add == 0:\n",
    "                ans = ans + ' '+  ele\n",
    "        return ans[1:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceWords(self, dictionary: List[str], sentence: str) -> str:\n",
    "        sentence+=\" \"\n",
    "        sub_match=\"\"\n",
    "        res=\"\"\n",
    "        flag=0\n",
    "        repeat=0\n",
    "        for s in sentence:\n",
    "            if s==' ':\n",
    "                if flag==0:\n",
    "                    res+=\"\".join(sub_match)\n",
    "                res+=\" \"\n",
    "                flag=0\n",
    "                repeat=0\n",
    "                sub_match=\"\"\n",
    "            else:\n",
    "                sub_match+=\"\".join(s)\n",
    "                if sub_match in dictionary:\n",
    "                    if repeat==0:\n",
    "                        res+=\"\".join(sub_match)\n",
    "                        repeat=1\n",
    "                    flag=1\n",
    "        return res[:-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def replaceWords(self, dictionary: List[str], sentence: str) -> str:\n",
    "      sentence1 = sentence.split(\" \")\n",
    "      dictionary.sort()\n",
    "      for i, char in enumerate(sentence1): # char是字符串\n",
    "          for j, item in enumerate(dictionary): # item是字符串\n",
    "              if char.startswith(item):\n",
    "                  sentence1[i] = item\n",
    "                  break\n",
    "        \n",
    "      return \" \".join(sentence1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceWords(self, dictionary: List[str], sentence: str) -> str:\n",
    "        # Brute force solution\n",
    "        dictionary.sort(key = lambda x: len(x))\n",
    "        words = sentence.split()\n",
    "        mod_words = []\n",
    "\n",
    "        for word in words:\n",
    "            for root in dictionary:\n",
    "                if word.startswith(root):\n",
    "                    word = root\n",
    "                    break\n",
    "            mod_words.append(word)\n",
    "        \n",
    "        return ' '.join(mod_words)\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.dict={}\n",
    "\n",
    "    def update(self,word):\n",
    "        t=self.dict\n",
    "        for w in word:\n",
    "            if w not in t:\n",
    "                t[w]={}\n",
    "            t=t[w]\n",
    "        t[\"end\"]=True\n",
    "    \n",
    "    def query(self,word):\n",
    "        t=self.dict\n",
    "        for w in word:\n",
    "            if w not in t:\n",
    "                return False\n",
    "            t=t[w]\n",
    "        return \"end\" in t\n",
    "\n",
    "    def query_prefix(self,word):\n",
    "        t=self.dict\n",
    "        ans=\"\"\n",
    "        for w in word:\n",
    "            if w not in t:\n",
    "                return \"\"\n",
    "            ans+=w\n",
    "            t=t[w]\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def replaceWords(self, dict: List[str], sentence: str) -> str:\n",
    "        # word_list=sentence.split(\" \")\n",
    "        # dict=set(dict)\n",
    "        # for i,word in enumerate(word_list):\n",
    "        #     for j in range(1,len(word)+1):\n",
    "        #         if word[:j] in dict:\n",
    "        #             word_list[i]=word[:j]\n",
    "        #             break\n",
    "        # return \" \".join(word_list)\n",
    "        word_list=sentence.split(\" \")\n",
    "        dict.sort(key=lambda x:len(x))\n",
    "        for i,word in enumerate(word_list):\n",
    "            t=Trie()\n",
    "            t.update(word)\n",
    "            for d in dict:\n",
    "                if t.query_prefix(d):\n",
    "                    word_list[i]=t.query_prefix(d)\n",
    "                    break\n",
    "        return \" \".join(word_list)\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceWords(self, dictionary: List[str], sentence: str) -> str:\n",
    "        char_dict = collections.defaultdict(int)\n",
    "        for c in dictionary:\n",
    "            char_dict[c] = len(c)\n",
    "\n",
    "        res = []\n",
    "        for s in sentence.split(\" \"):\n",
    "            tmp = \"\"\n",
    "            for i in range(len(s)):\n",
    "                tmp = tmp + s[i]\n",
    "                tmp_len = char_dict.get(tmp)\n",
    "                if tmp_len is not None:\n",
    "                    res.append(tmp)\n",
    "                    break\n",
    "                if i == len(s) - 1:\n",
    "                    res.append(tmp)\n",
    "\n",
    "        return \" \".join(res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceWords(self, dictionary: List[str], sentence: str) -> str:\n",
    "        heads = set()\n",
    "        mydictionary = set(dictionary)\n",
    "\n",
    "        for w in dictionary:\n",
    "            for i in range(1,len(w)+1):\n",
    "                heads.add(w[:i])\n",
    "        \n",
    "        ans = sentence.split()\n",
    "\n",
    "        for j in range(len(ans)):\n",
    "            w = ans[j]\n",
    "            for i in range(1,len(w)+1):\n",
    "                if w[:i] not in heads:\n",
    "                    break\n",
    "                elif w[:i] in mydictionary:\n",
    "                    ans[j] = w[:i]\n",
    "                    break\n",
    "        return ' '.join(ans)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceWords(self, dict: List[str], sentence: str) -> str:\n",
    "        tree = {}\n",
    "\n",
    "        for word in dict:\n",
    "            tmptree = tree\n",
    "            for ch in word:\n",
    "                if ch not in tmptree:\n",
    "                    tmptree[ch] = {}\n",
    "                tmptree = tmptree[ch]\n",
    "            tmptree[\"#\"] = \"#\"\n",
    "        \n",
    "        words = sentence.split(\" \")\n",
    "        stack = []\n",
    "        for word in words:\n",
    "            flag, root = self.startWith(word, tree)\n",
    "            #print(flag)\n",
    "            if flag:\n",
    "                stack.append(root)\n",
    "            else:\n",
    "                stack.append(word)\n",
    "        #print(stack)\n",
    "        return \" \".join(stack)\n",
    "\n",
    "\n",
    "    def startWith(self, word, tree):\n",
    "        res = \"\"\n",
    "        for ch in word:\n",
    "            #print(tree)\n",
    "            if isinstance(tree, dict) and \"#\" in tree:\n",
    "                return True, res\n",
    "            if ch not in tree:\n",
    "                return False, \"\"\n",
    "            tree = tree[ch]\n",
    "            res = res + ch\n",
    "        if isinstance(tree, dict) and \"#\" not in tree:\n",
    "            return False, \"\"\n",
    "        else:\n",
    "            return True, word\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.trie_dict = {}\n",
    "    \n",
    "    def add(self, word):\n",
    "        current = self.trie_dict\n",
    "        for i in range(len(word)):\n",
    "            c, nc = word[i], \"|\" if i >= len(word) - 1 else word[i + 1]\n",
    "            current = current.setdefault(c, {})\n",
    "            current[nc] = {}\n",
    "    \n",
    "    def query(self, word):\n",
    "        current = self.trie_dict\n",
    "        prefix = []\n",
    "        for c in word:\n",
    "            if c not in current:\n",
    "                return word\n",
    "            current = current[c]\n",
    "            prefix.append(c)\n",
    "            if \"|\" in current:\n",
    "                return \"\".join(prefix)\n",
    "        return word\n",
    "\n",
    "class Solution:\n",
    "    def replaceWords(self, dictionary: List[str], sentence: str) -> str:\n",
    "        words = sentence.split()\n",
    "        dictionary = set(dictionary)\n",
    "        trie = Trie()\n",
    "        for word in dictionary:\n",
    "            trie.add(word)\n",
    "        # print(trie.trie_dict)\n",
    "        return \" \".join([trie.query(word) for word in words])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceWords(self, dictionary: List[str], sentence: str) -> str:\n",
    "        #构建字典树\n",
    "        d = {}\n",
    "        for word in dictionary:\n",
    "            t = d#为什么要这样，因为每遍历一个word后需要重新回到原字典的最外层，创造第二个word的分支\n",
    "            for chr in word:\n",
    "                if chr not in t:\n",
    "                    t[chr] = {}\n",
    "                t = t[chr]\n",
    "            t['end'] = True#只有词根的最后一个元素对应的{}才有‘end’\n",
    "        def f(word):\n",
    "            t = d\n",
    "            for i,chr in enumerate(word):\n",
    "                if 'end' in t:#这里必须先判断‘end’ ，如果先判断not in，则会break返回原单词，for循环中只有true才能返回前缀，循环结束就一定是没有\n",
    "                    #考虑下有没有其他的方式\n",
    "                    return word[:i]\n",
    "                elif chr not in t:\n",
    "                    break\n",
    "                t = t[chr]\n",
    "            return word\n",
    "        return ' '.join(map(f,sentence.split(' ')))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceWords(self, dictionary: List[str], sentence: str) -> str:\n",
    "        trie = Trie()\n",
    "        for word in dictionary:\n",
    "            trie.insert(word)\n",
    "\n",
    "        res = []\n",
    "        for word in sentence.split():\n",
    "            if trie.start_witch(word):\n",
    "                res.append(trie.start_witch(word))\n",
    "            else:\n",
    "                res.append(word)\n",
    "\n",
    "        return ' '.join(res)\n",
    "\n",
    "\n",
    "class Trie():\n",
    "\n",
    "    def __init__(self):\n",
    "        self.data = {}\n",
    "        self.end = '#'\n",
    "\n",
    "    def insert(self, word):\n",
    "        node = self.data\n",
    "        for char in word:\n",
    "            if char not in node:\n",
    "                node[char] = {}\n",
    "            node = node[char]\n",
    "        node[self.end] = 1\n",
    "\n",
    "    def start_witch(self, pre_fix):\n",
    "        node = self.data\n",
    "        res = ''\n",
    "        for char in pre_fix:\n",
    "            if char not in node:\n",
    "                return False\n",
    "            if char in node:\n",
    "                res += char\n",
    "            node = node[char]\n",
    "            if self.end in node:\n",
    "                break            \n",
    "\n",
    "        return res\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    def __init__(self):\n",
    "        self.end = False\n",
    "        self.child = defaultdict(Node)\n",
    "\n",
    "    def insert(self,ins):\n",
    "        if ins == '':\n",
    "            return\n",
    "        if ins[0] not in self.child:\n",
    "            self.child[ins[0]]\n",
    "        cur = self.child[ins[0]]\n",
    "        for i in range(1,len(ins)):\n",
    "            cur.child[ins[i]] = Node()\n",
    "            cur = cur.child[ins[i]]\n",
    "        cur.end = True\n",
    "\n",
    "    def query(self,q):\n",
    "        res = ''\n",
    "        cur = self\n",
    "        for i in q:\n",
    "            if cur.end:\n",
    "                return res\n",
    "            if i not in cur.child:\n",
    "                return q\n",
    "            else:\n",
    "                cur = cur.child[i]\n",
    "            res += i\n",
    "        return res\n",
    "\n",
    "class Solution:\n",
    "    def replaceWords(self, dictionary: List[str], sentence: str) -> str:\n",
    "        root = Node()\n",
    "        for d in dictionary:\n",
    "            root.insert(d)\n",
    "        return ' '.join(map(root.query,sentence.split(' ')))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceWords(self, dictionary: List[str], sentence: str) -> str:\n",
    "        # trie tree method\n",
    "        trie = {}\n",
    "        for d in dictionary:\n",
    "            node = trie\n",
    "            for ch in d:\n",
    "                if ch not in node:\n",
    "                    node[ch] = {}\n",
    "                node = node[ch]\n",
    "            node['END'] = {}\n",
    "        words = sentence.split()\n",
    "        for i, w in enumerate(words):\n",
    "            node = trie\n",
    "            for j, ch in enumerate(w):\n",
    "                if 'END' in node:\n",
    "                    words[i] = w[:j]\n",
    "                    break\n",
    "                if ch not in node:\n",
    "                    break\n",
    "                node = node[ch]\n",
    "        return ' '.join(words)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceWords(self, dictionary: List[str], sentence: str) -> str:\n",
    "        trie = {}               #定义一个字典树\n",
    "        for word in dictionary:     #把dictionary中的每个单词的字母存入字典树\n",
    "            tree = trie             #tree指向字典树\n",
    "            for char in word:           #遍历word中的每个字母\n",
    "                if char not in tree:        #如果不在字典树中\n",
    "                    tree[char] = {}     #字典树中增加key值\n",
    "                tree = tree[char]       #把tree指向下一个节点\n",
    "            tree['#'] = '#'         #遍历完以后，把#加入节点，表示单词遍历结束\n",
    "        \n",
    "        sentence = sentence.split(' ')      #分割句子      \n",
    "        res = []        #定义结果值\n",
    "        for word in sentence:       #遍历整个句子\n",
    "            tree = trie             #tree指向字典树\n",
    "            tmp_res = \"\"            #定义一个临时的字符串结果，用来存储匹配到的前缀字符\n",
    "            for char in word:       #遍历word\n",
    "                if char not in tree:        #如果已经不在tree中了，说明已经不符合条件，直接break\n",
    "                    break\n",
    "                else:\n",
    "                    tmp_res += char             #如果在里面，则把匹配到的前缀字符存起来\n",
    "                    tree = tree[char]       #同时把tree移动到下一个节点\n",
    "                    if '#' in tree:     #由于题目中要求如果有多个词根，使用最短的，那么移动到下一个的节点时，就要判断#是否在tree中，如果已经在了，说明已经找到了最短的词根，就要退出，不需要再进行查找\n",
    "                        break                    \n",
    "            #当都遍历完以后，有2种情况，一种是在下一个节点中不存在#,说明没任何词根可以匹配这个单词的前缀，那么就把整个word作为内容存入res\n",
    "            #如果下一个节点中有#,说明有完整的词根可以匹配做这个单词的前缀，那么就把之前存储的tmp_res前缀存入res\n",
    "            if '#' not in tree:         \n",
    "                res.append(word)\n",
    "            else:\n",
    "                res.append(tmp_res)\n",
    "        return ' '.join(res)        #最后连接结果输出即可\n",
    "\n",
    "                    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceWords(self, dictionary: List[str], sentence: str) -> str:\n",
    "        trie = Trie()\n",
    "        for word in dictionary:\n",
    "            trie.insert(word)\n",
    "\n",
    "        res = []\n",
    "        sentence_list = sentence.strip().split(' ')\n",
    "        dictionary_set = set(dictionary)\n",
    "        # print(sentence_list)\n",
    "        # print(dictionary_set)\n",
    "        for word in sentence_list:\n",
    "            current_res = trie.find_and_output(word, dictionary_set)\n",
    "            if not current_res:\n",
    "                res.append(word)\n",
    "            else:\n",
    "                res.append(current_res)\n",
    "\n",
    "        # print(res)\n",
    "        return ' '.join(res)\n",
    "\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.root = {}\n",
    "\n",
    "    def insert(self, word):\n",
    "        node = self.root\n",
    "        for w in word:\n",
    "            if w not in node:\n",
    "                node[w] = {}\n",
    "                node = node[w]\n",
    "            else:\n",
    "                node = node[w]\n",
    "\n",
    "        return self.root\n",
    "\n",
    "    def find_and_output(self, cg, dict_):\n",
    "        node = self.root\n",
    "        res = ''\n",
    "        for c in cg:\n",
    "            if c not in node:\n",
    "                return res if res in dict_ else ''\n",
    "            else:\n",
    "                node = node[c]\n",
    "                res = res + c\n",
    "                if res in dict_:\n",
    "                    return res\n",
    "\n",
    "        return ''\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceWords(self, dictionary: List[str], sentence: str) -> str:\n",
    "        # sentence=sentence.split()\n",
    "        # for i,j in enumerate(sentence):\n",
    "        #     tmp=\"\"\n",
    "        #     for c in j:\n",
    "        #         tmp+=c\n",
    "        #         if tmp in dictionary:\n",
    "        #             sentence[i]=tmp\n",
    "        #             break\n",
    "        # return \" \".join(sentence)\n",
    "        trie={}\n",
    "        sentence=sentence.split()\n",
    "        for word in dictionary:\n",
    "            now=trie\n",
    "            for w in word:\n",
    "                if w not in now:\n",
    "                    now[w]={}\n",
    "                now=now[w]\n",
    "            now['#']={}\n",
    "        # 当你在循环中使用 for word in sentence 时，word 变量是对句子中单词的临时副本，而不是直接引用\n",
    "        # 原始句子中的单词。因此，当你修改 word 时，并不会影响原始的 sentence 列表。\n",
    "        # 所以要使用sentence[i]=word[:j+1]\n",
    "        for i,word in enumerate(sentence):\n",
    "            now=trie\n",
    "            for j,w in enumerate(word):\n",
    "                if w not in now:\n",
    "                    break\n",
    "                if '#' in now[w]:\n",
    "                    sentence[i]=word[:j+1]\n",
    "                    # word=word[:j+1]\n",
    "                    break\n",
    "                now=now[w]\n",
    "        return \" \".join(sentence)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Tree:\n",
    "    def __init__(self):\n",
    "        self.tree = {'is_end': False}\n",
    "        pass\n",
    "    \n",
    "    def add_word(self, word):\n",
    "        root = self.tree\n",
    "        for c in word:\n",
    "            if c not in root:\n",
    "                root[c] = {'is_end': False}\n",
    "            root = root[c]\n",
    "        root['is_end'] = True\n",
    "\n",
    "    def has_prefix(self, word):\n",
    "        root = self.tree\n",
    "        for c in word:\n",
    "            if c in root:\n",
    "                root = root[c]\n",
    "                if root['is_end']:\n",
    "                    return True\n",
    "            else:\n",
    "                return root['is_end']\n",
    "        return root['is_end']\n",
    "\n",
    "    def get_prefix(self, word):\n",
    "        root = self.tree\n",
    "        result = ''\n",
    "        for c in word:\n",
    "            if c in root:\n",
    "                root = root[c]\n",
    "                result += c\n",
    "                if root['is_end']:\n",
    "                    return result\n",
    "            else:\n",
    "                return result\n",
    "        return word\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def replaceWords(self, dictionary: List[str], sentence: str) -> str:\n",
    "        tree = Tree()\n",
    "        for word in dictionary:\n",
    "            tree.add_word(word)\n",
    "        result = []\n",
    "        for word in sentence.split(' '):\n",
    "            if tree.has_prefix(word):\n",
    "                result.append(tree.get_prefix(word))\n",
    "            else:\n",
    "                result.append(word)\n",
    "        return ' '.join(result)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceWords(self, dictionary: List[str], sentence: str) -> str:\n",
    "        dictionary.sort(reverse=True)\n",
    "        trie = {}\n",
    "        for word in dictionary:\n",
    "            cur = trie\n",
    "            for i in range(len(word)):\n",
    "                if word[i] in cur:\n",
    "                    if i==len(word)-1:\n",
    "                        cur[word[i]] = {}\n",
    "                        break\n",
    "                    cur = cur[word[i]]\n",
    "                else:\n",
    "                    cur[word[i]] = {}\n",
    "                    cur = cur[word[i]]\n",
    "        res = \"\"\n",
    "        for word in sentence.split(\" \"):\n",
    "            cur = trie\n",
    "            new_word = \"\"\n",
    "            for w in word:\n",
    "                if w in cur:\n",
    "                    new_word = new_word+w\n",
    "                else:\n",
    "                    break\n",
    "                cur = cur[w]\n",
    "            if len(cur)==0:\n",
    "                res = res + new_word + \" \"\n",
    "            else:\n",
    "                res = res + word + \" \"\n",
    "        return res[:-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.child = collections.defaultdict(dict)\n",
    "    def insert(self, words):\n",
    "        cur = self.child\n",
    "        for word in words:\n",
    "            if word not in cur.keys():\n",
    "                cur[word] = collections.defaultdict(dict)\n",
    "            cur = cur[word]\n",
    "        cur['#'] = '#'\n",
    "    def startwith(self, words):\n",
    "        w = []\n",
    "        cur = self.child\n",
    "        for word in words:\n",
    "            if '#' in cur.keys():\n",
    "                return ''.join(w)\n",
    "            elif word not in cur.keys():\n",
    "                return words\n",
    "            w.append(word)\n",
    "            cur = cur[word]\n",
    "        else:\n",
    "            return words\n",
    "            \n",
    "\n",
    "class Solution:\n",
    "    def replaceWords(self, dictionary: List[str], sentence: str) -> str:\n",
    "        book = Trie()\n",
    "        for word in dictionary:\n",
    "            book.insert(word)\n",
    "\n",
    "        words = sentence.split()\n",
    "        ans = []\n",
    "        for word in words:\n",
    "            ans.append(book.startwith(word))\n",
    "        return ' '.join(ans)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "# class TrieNode:\n",
    "#     def __init__(self, val = None, isEnd = False):\n",
    "#         self.val = val\n",
    "#         self.isEnd = isEnd\n",
    "#         self.children = {}\n",
    "\n",
    "# class Solution:\n",
    "#     def replaceWords(self, dictionary: List[str], sentence: str) -> str:\n",
    "#         def insertWord(word):\n",
    "#             cur = root\n",
    "#             for w in word:\n",
    "#                 if w not in cur.children:\n",
    "#                     cur.children[w] = TrieNode(w, False)\n",
    "#                 cur = cur.children[w]\n",
    "#             cur.isEnd = True\n",
    "        \n",
    "#         def find(word):\n",
    "#             cur = root\n",
    "#             res = []\n",
    "#             for w in word:\n",
    "#                 if cur.isEnd:\n",
    "#                     return \"\".join(res)\n",
    "#                 if w not in cur.children:\n",
    "#                     return word\n",
    "#                 res.append(w)\n",
    "#                 cur = cur.children[w]\n",
    "#             else:\n",
    "#                 return \"\".join(res)\n",
    "\n",
    "#         root = TrieNode(\"\")\n",
    "#         for word in dictionary:\n",
    "#             insertWord(word)\n",
    "#         words = sentence.split()\n",
    "#         res = []\n",
    "#         for word in words:\n",
    "#             res.append(find(word))\n",
    "#         return \" \".join(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    __slots__ = 'ch','val'\n",
    "    def __init__(self):\n",
    "        self.ch = defaultdict(Node)\n",
    "        self.val = 0\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self, dictionary):\n",
    "        self.root = Node()\n",
    "        for c in dictionary:\n",
    "            self.insert(c)\n",
    "\n",
    "    def insert(self, word) -> None:\n",
    "        cur = self.root\n",
    "        for c in word:\n",
    "            cur = cur.ch[c]\n",
    "        cur.val += 1\n",
    "    \n",
    "    def query(self, word) -> str:\n",
    "        cur = self.root\n",
    "        for i, c in enumerate(word):\n",
    "            if cur.val > 0:\n",
    "                return word[:i]\n",
    "            if c not in cur.ch:\n",
    "                return word\n",
    "            cur = cur.ch[c]\n",
    "        return word\n",
    "        \n",
    "class Solution:\n",
    "    def replaceWords(self, dictionary: List[str], sentence: str) -> str:\n",
    "        tr = Trie(dictionary)\n",
    "        return \" \".join(tr.query(word) for word in sentence.split())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceWords(self, dictionary: List[str], sentence: str) -> str:\n",
    "        res = []\n",
    "        dictionary = sorted(dictionary, key=lambda x: len(x))\n",
    "        sub_str = '^' + '|^'.join(dictionary)\n",
    "        for i in sentence.split():\n",
    "            temp = re.findall(sub_str, i)\n",
    "            if temp:\n",
    "                res.append(temp[0])\n",
    "            else:\n",
    "                res.append(i)\n",
    "        return ' '.join(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceWords(self, dictionary: List[str], sentence: str) -> str:\n",
    "        trie = Trie()\n",
    "\n",
    "        for dic in dictionary:\n",
    "            trie.insert(dic)\n",
    "\n",
    "        res = \"\"\n",
    "        for sen in sentence.split(\" \"):\n",
    "            res += trie.query(sen) + \" \"\n",
    "\n",
    "        return res[0: -1]\n",
    "\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.root = [0, {}]\n",
    "\n",
    "    def insert(self, word):\n",
    "        cur = self.root\n",
    "\n",
    "        for c in word:\n",
    "            if c not in cur[1]:\n",
    "                cur[1][c] = [0, {}]\n",
    "\n",
    "            cur = cur[1][c]\n",
    "\n",
    "        cur[0] += 1\n",
    "\n",
    "    def query(self, word):\n",
    "        cur = self.root\n",
    "        n = len(word)\n",
    "\n",
    "        for i in range(n):\n",
    "            c = word[i]\n",
    "            if c in cur[1]:\n",
    "                cur = cur[1][c]\n",
    "                if cur[0] >= 1:\n",
    "                    return word[:i+1]\n",
    "            else:\n",
    "                break    \n",
    "            \n",
    "        return word\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    __slots__ = 'children', 'root'\n",
    "    def __init__(self):\n",
    "        self.children = defaultdict(Trie)\n",
    "        self.root = ''\n",
    "\n",
    "    def insert(self, word):\n",
    "        cur = self\n",
    "        for ch in word:\n",
    "            cur = cur.children[ch]\n",
    "        cur.root = word\n",
    "\n",
    "    def query(self, word):\n",
    "        cur = self\n",
    "        for ch in word:\n",
    "            if ch not in cur.children:\n",
    "                return word\n",
    "            cur = cur.children[ch]\n",
    "            if cur.root:\n",
    "                return cur.root\n",
    "        return word\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def replaceWords(self, dictionary: List[str], sentence: str) -> str:\n",
    "        root = Trie()\n",
    "        for word in dictionary:\n",
    "            root.insert(word)\n",
    "        \n",
    "        ans = []\n",
    "        for word in sentence.split():\n",
    "            ans.append(root.query(word))\n",
    "        return ' '.join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef replaceWords(self, dictionary, sentence):\n",
    "\t\ttrie, ans = [{}, 0], []\n",
    "\t\tfor s in dictionary:\n",
    "\t\t\tt, n = trie, 0\n",
    "\t\t\tfor c in s:\n",
    "\t\t\t\tif c not in t[0]: t[0][c] = [{}, 0]\n",
    "\t\t\t\tt, n = t[0][c], n + 1\n",
    "\t\t\tt[1] = n\n",
    "\t\tfor s in sentence.split():\n",
    "\t\t\tt, n = trie, 0\n",
    "\t\t\tfor c in s:\n",
    "\t\t\t\tif c not in t[0]: break\n",
    "\t\t\t\tt = t[0][c]\n",
    "\t\t\t\tif t[1] > 0: n = t[1]; break\n",
    "\t\t\tans.append(s[:n] if n > 0 else s)\n",
    "\t\treturn ' '.join(ans)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "Trie = lambda: collections.defaultdict(Trie)\n",
    "class Solution:\n",
    "    def replaceWords(self, dictionary: List[str], sentence: str) -> str:\n",
    "        root = Trie()\n",
    "        for prefix in dictionary:\n",
    "            prefix += '#'\n",
    "            T = root\n",
    "            for ch in prefix:\n",
    "                T = T[ch]\n",
    "        print(root)\n",
    "        \n",
    "        sentence = sentence.split()\n",
    "        n = len(sentence)\n",
    "        for i, word in enumerate(sentence):\n",
    "            T = root\n",
    "            new_word = ''\n",
    "            for ch in word:\n",
    "                if '#' in T:\n",
    "                    sentence[i] = new_word\n",
    "                    break\n",
    "                if ch not in T:\n",
    "                    break\n",
    "                new_word += ch\n",
    "                T = T[ch]\n",
    "        #print(sentence)\n",
    "        return ' '.join(sentence)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "Trie = lambda:defaultdict(Trie)\n",
    "\n",
    "class Solution:\n",
    "    def replaceWords(self, dictionary: List[str], sentence: str) -> str:\n",
    "        trie = Trie()\n",
    "        for word in dictionary:\n",
    "            p = trie\n",
    "            for e in word:\n",
    "                p = p[e]\n",
    "            p['#'] = 1\n",
    "\n",
    "        arr = []\n",
    "        trimFlag, notFoundFlag = False, False\n",
    "        p = trie\n",
    "        for e in sentence:\n",
    "            if e == ' ':\n",
    "                trimFlag = False\n",
    "                notFoundFlag = False\n",
    "                arr.append(e)\n",
    "                p = trie\n",
    "                continue\n",
    "            if trimFlag: continue\n",
    "            arr.append(e)\n",
    "            if notFoundFlag: continue\n",
    "            if e not in p:\n",
    "                notFoundFlag = True\n",
    "            else:\n",
    "                p = p[e]\n",
    "                if '#' in p: trimFlag = True\n",
    "        return ''.join(arr)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    class TrieNode(collections.defaultdict):\n",
    "        def __init__(self):\n",
    "            super().__init__(Trie.TrieNode)\n",
    "            self.eow=False\n",
    "    def __init__(self):\n",
    "        self.root=Trie.TrieNode()\n",
    "\n",
    "    def insert(self,word):\n",
    "        node=self.root\n",
    "        for char in word:\n",
    "            node=node[char]\n",
    "        node.eow=True\n",
    "    def replace(self,word):\n",
    "            node=self.root\n",
    "            for i,char in enumerate(word):\n",
    "                if char not in node:\n",
    "                    return word\n",
    "                node=node[char]\n",
    "                if node.eow:return word[:i+1]\n",
    "            return word\n",
    "    \n",
    "\n",
    "class Solution:\n",
    "    def replaceWords(self, prefixes: List[str], sentence: str) -> str:\n",
    "        trie=Trie()\n",
    "        for prefix in prefixes:\n",
    "            trie.insert(prefix)\n",
    "        return ' '.join( map(trie.replace,sentence.split()) )"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.children = {}\n",
    "        self.is_end = False\n",
    "    \n",
    "    def insert(self, prefix):\n",
    "        cur = self\n",
    "        for s in prefix:\n",
    "            if s not in cur.children:\n",
    "                cur.children[s] = Trie()\n",
    "            cur = cur.children[s]\n",
    "        cur.is_end = True\n",
    "    \n",
    "    def search(self, word):\n",
    "        cur, count = self, 0\n",
    "        for s in word:\n",
    "            if cur.is_end:\n",
    "                return word[:count]\n",
    "            elif s not in cur.children:\n",
    "                return word \n",
    "            count += 1\n",
    "            cur = cur.children[s]\n",
    "        return word\n",
    "\n",
    "class Solution:\n",
    "    def replaceWords(self, dictionary: List[str], sentence: str) -> str:\n",
    "        dic = Trie()\n",
    "        for prefix in dictionary:\n",
    "            dic.insert(prefix)\n",
    "        \n",
    "        words, res = sentence.split(' '), []\n",
    "        for word in words:\n",
    "            res.append(dic.search(word))\n",
    "        return ' '.join(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    def __init__(self, value):\n",
    "        self.value = value\n",
    "        self.isLeaf = False\n",
    "        self.children = []\n",
    "        self.children_char = []\n",
    "    \n",
    "    def set_is_leaf(self):\n",
    "        self.isLeaf = True\n",
    "        \n",
    "    \n",
    "class Tree:\n",
    "    def __init__(self):\n",
    "        self.rootNode = Node('0')\n",
    "    \n",
    "    def insertNode(self, parent, childChar):\n",
    "        child = Node(childChar)\n",
    "        parent.children.append(child)\n",
    "        parent.children_char.append(childChar)\n",
    "        return child\n",
    "\n",
    "    def deleteChildren(self, parent):\n",
    "        parent.children = []\n",
    "        parent.children_char = []\n",
    "    \n",
    "    def findRoot(self, voc):\n",
    "        p = self.rootNode\n",
    "        vocRoot = \"\"\n",
    "        for i in voc:\n",
    "            if i in p.children_char and not p.isLeaf:\n",
    "                for child in p.children:\n",
    "                    if i == child.value:\n",
    "                        p = child\n",
    "                        vocRoot = vocRoot + i\n",
    "            else:\n",
    "                break\n",
    "\n",
    "        if p.isLeaf:\n",
    "            return vocRoot\n",
    "        else:\n",
    "            return voc\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def replaceWords(self, dictionary: List[str], sentence: str) -> str:\n",
    "        rootTree = Tree()\n",
    "        for root in dictionary:\n",
    "            p = rootTree.rootNode\n",
    "            for i in root:\n",
    "                if p.isLeaf: #是叶子结点就不继续了\n",
    "                        break\n",
    "\n",
    "                if i in p.children_char:\n",
    "                    for child in p.children:\n",
    "                        if i == child.value:\n",
    "                            p = child\n",
    "                else:\n",
    "                    child = rootTree.insertNode(p, i)\n",
    "                    p = child\n",
    "            \n",
    "            p.set_is_leaf()\n",
    "            rootTree.deleteChildren(p)\n",
    "\n",
    "        word_list = sentence.split()\n",
    "        result_list = []\n",
    "        for word in word_list:\n",
    "            result = rootTree.findRoot(word)\n",
    "            result_list.append(result)\n",
    "\n",
    "        changed_sentence = \"\"\n",
    "        for i in range(len(result_list) - 1):\n",
    "            changed_sentence = changed_sentence + result_list[i] + \" \"\n",
    "        changed_sentence = changed_sentence + result_list[-1]\n",
    "        return changed_sentence\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class treeNode:\n",
    "    def __init__(self):\n",
    "        self.children = {}\n",
    "        self.valid = False\n",
    "class Solution:\n",
    "    def replaceWords(self, dictionary: List[str], sentence: str) -> str:\n",
    "        node = treeNode()\n",
    "        for word in dictionary:\n",
    "            now = node\n",
    "            for l in word:\n",
    "                if l not in now.children:\n",
    "                    now.children[l] = treeNode()\n",
    "                now = now.children[l]\n",
    "            now.valid = True\n",
    "        sentenceList = list(map(str,sentence.split()))\n",
    "        result = []\n",
    "        for word in sentenceList:\n",
    "            path = ''\n",
    "            now = node\n",
    "            flag = 0\n",
    "            for l in word:\n",
    "                if now.valid ==True:\n",
    "                    result.append(path)\n",
    "                    flag = 1\n",
    "                    break\n",
    "                if l not in now.children:\n",
    "                    result.append(word)\n",
    "                    flag = 1\n",
    "                    break\n",
    "                if l in now.children:\n",
    "                    path+=l\n",
    "                    now = now.children[l]\n",
    "            if flag==0:\n",
    "                result.append(path)\n",
    "        return  ' '.join(result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class TrieNode:\n",
    "    def __init__(self):\n",
    "        self.children = {}\n",
    "        self.endOfWord = False\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.root = TrieNode()\n",
    "\n",
    "    def insert(self, word):\n",
    "        cur = self.root\n",
    "        for c in word:\n",
    "            if c not in cur.children:\n",
    "                cur.children[c] = TrieNode()\n",
    "            cur = cur.children[c]\n",
    "        cur.endOfWord = True\n",
    "\n",
    "    def search(self, word):\n",
    "        cur = self.root\n",
    "        for c in word:\n",
    "            if c not in cur.children:\n",
    "                return False\n",
    "            cur = cur.children[c]\n",
    "        return cur.endOfWord == True\n",
    "\n",
    "class Solution:\n",
    "    def replaceWords(self, dictionary: List[str], sentence: str) -> str:\n",
    "        t = Trie()\n",
    "        for word in dictionary:\n",
    "            t.insert(word)\n",
    "\n",
    "        words = sentence.split(' ')\n",
    "        dictionary = set(dictionary)\n",
    "        for i, w in enumerate(words):\n",
    "            for j in range(len(w)):\n",
    "                if w[:j+1] in dictionary:\n",
    "                    words[i] = w[:j+1]\n",
    "                    break\n",
    "        return ' '.join(words)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class NODE:\n",
    "    def __init__(self):\n",
    "        self.children = dict()\n",
    "        self.flag = False\n",
    "\n",
    "class Solution:\n",
    "    def replaceWords(self, dictionary: List[str], sentence: str) -> str:\n",
    "        root = NODE()\n",
    "        def add_word(s):\n",
    "            t = root\n",
    "            for c in s:\n",
    "                if c not in t.children:\n",
    "                    t.children[c] = NODE()\n",
    "                t = t.children[c]\n",
    "            t.flag = True\n",
    "\n",
    "        for s in dictionary:\n",
    "            add_word(s)\n",
    "        \n",
    "        def replace(s):\n",
    "            t = root\n",
    "            ts = \"\"\n",
    "            for c in s:\n",
    "                if t.flag:\n",
    "                    return ts\n",
    "                if c not in t.children:\n",
    "                    break\n",
    "                t = t.children[c]\n",
    "                ts += c\n",
    "            return s\n",
    "        arr = sentence.split()\n",
    "        ans = []\n",
    "        for s in arr:\n",
    "            ans.append(replace(s))\n",
    "        return \" \".join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class node:\n",
    "    def __init__(self):\n",
    "        self.child = defaultdict()\n",
    "        self.isend = False\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.root = node()\n",
    "    def addword(self, word):\n",
    "        cur = self.root\n",
    "        for w in word:\n",
    "            if w not in cur.child:\n",
    "                cur.child[w] = node()\n",
    "            cur = cur.child[w]\n",
    "        cur.isend = True\n",
    "\n",
    "    def searchword(self, word):\n",
    "        cur = self.root\n",
    "        for w in range(len(word)):\n",
    "            if word[w] not in cur.child:\n",
    "                return word\n",
    "            cur = cur.child[word[w]]\n",
    "            if cur.isend:\n",
    "                return word[:w + 1]\n",
    "        return word\n",
    "\n",
    "    def replaceWords(self, dictionary: List[str], sentence: str) -> str:\n",
    "        for i in dictionary:\n",
    "            self.addword(i)\n",
    "        sentence = sentence.split(\" \")\n",
    "        res = []\n",
    "        print()\n",
    "        for i in sentence:\n",
    "            res.append(self.searchword(i))\n",
    "        return \" \".join(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class node:\n",
    "    def __init__(self):\n",
    "        self.ch = [None] * 26\n",
    "        self.end = False\n",
    "class Solution:\n",
    "    def replaceWords(self, dictionary: List[str], sentence: str) -> str:\n",
    "        root = node()\n",
    "        for word in dictionary:\n",
    "            cur = root\n",
    "            for c in word:\n",
    "                v = ord(c) - ord('a')\n",
    "                if cur.ch[v] is None:\n",
    "                    cur.ch[v] = node()\n",
    "                cur = cur.ch[v]\n",
    "            cur.end = True\n",
    "        sentence = sentence.split(\" \")\n",
    "        ans = []\n",
    "        for s in sentence:\n",
    "            cur = root\n",
    "            curw = \"\"\n",
    "            for c in s:\n",
    "                v = ord(c) - ord('a')\n",
    "                cur = cur.ch[v]\n",
    "                curw += c\n",
    "                if cur is None:\n",
    "                    curw = s\n",
    "                    break\n",
    "                if cur.end:\n",
    "                    break\n",
    "                \n",
    "            ans.append(curw)\n",
    "        return \" \".join(ans)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
